#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"


void HPInit(HP* heap)
{
	assert(heap);
	heap->Capacity = 0;
	heap->size = 0;
	heap->data = NULL;
}


void HPDeastroy(HP* heap)
{
	assert(heap);
	free(heap->data);
	heap->data = NULL;
	heap->Capacity = 0;
	heap->size = 0;
}


void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType z;
	z = *x;
	*x = *y;
	*y = z;
}


void AdjustUp(HPDataType* a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

void HPPush(HP* heap, HPDataType x)
{
	assert(heap);
	if (heap->size == heap->Capacity)
	{
		int newCap = heap->Capacity == 0 ? 4 : heap->Capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(heap->data, sizeof(HPDataType) * newCap);
		assert(tmp);
		heap->data = tmp;
		heap->Capacity = newCap;
	}
	heap->data[heap->size] = x;
	heap->size++;

	AdjustUp(heap->data, heap->size - 1);
}

void AdjustDown(HPDataType* a, int size, int parent)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child + 1] > a[child])
			++child;

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

void HPPop(HP* heap)
{
	assert(heap);
	assert(heap->size > 0);
	Swap(&heap->data[0], &heap->data[heap->size - 1]);
	heap->size--;
	AdjustDown(heap->data, heap->size, 0);
}

int HPSize(HP* heap)
{
	assert(heap);
	return heap->size;
}

bool HPEmpty(HP* heap)
{
	assert(heap);
	return heap->size == 0;
}

HPDataType HPTop(HP* heap)
{
	assert(heap);
	assert(heap->size > 0);
	return heap->data[0];
}

void HeapSort(HPDataType* a, int n)
{
	for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

//void CreateNDate()
//{
//	int n = 100000;
//	srand(time(0));
//	const char* file = "data.txt";
//	FILE* fin = fopen(file, "w");
//	if (fin == NULL)
//	{
//		perror("fopen error");
//		return;
//	}
//	for (int i = 0; i < n; i++)
//	{
//		int x = (rand() + i) % 100000;
//		fprintf(fin, "%d\n", x);
//	}
//	fclose(fin);
//}

void CreateNDate()
{
	int n = 100000;
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	srand((unsigned int)time(0));
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		int x = (rand() + i) % 100000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

void PrintTopK(const char* file, int k)
{
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}
	
	int* heap = (int*)malloc(sizeof(int) * k);
	if (heap == NULL)
	{
		perror("malloc error");
		return;
	}

	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &heap[i]);
		AdjustUp(heap, i);
	}

	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > heap[0])
		{
			heap[0] = x;
			AdjustDown(heap, k, 0);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", heap[i]);
	}
	printf("\n");
	free(heap);
	fclose(fout);
}


//void HeapSort(HPDataType* a, int n)
//{
//	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
//	{
//		AdjustDown(a, n, i);
//	}
//	int end = n - 1;
//	while (end > 0)
//	{
//		Swap(&a[0], &a[end]);
//		AdjustDown(a, end, 0);
//		--end;
//	}
//}
//
//void AdjustUp(HP* heap)
//{
//	assert(heap);
//	int child = heap->size - 1;
//	int parent = (child - 1) / 2;
//	while(child > 0)
//	{
//		if (heap->data[child] < heap->data[parent])
//		{
//			Swap(&heap->data[child], heap->data[parent]);
//			child = parent;
//			parent = (child - 1) / 2;
//		}
//		else
//			break;
//	}
//}